package com.lims.algorithm.algset.dp;

/**
 * <功能简述> 在数组中找出和一定的数的所有组合
 *
 * @author lims
 * @date 2020-05-26 15:16
 */
public class FixedSumInArr {
    public static void main(String[] args) {
        int n = 5;
        int[] inputData = {1, 2, 3, 4, 3};
        int[] marksArr = new int[5];
        findCombine(n, inputData, marksArr, 5);
    }

    public static void findCombine(int n, int inputData[], int marksArr[], int size) {
        findCombine(n, inputData, 0, size, marksArr, -1, size, false);
    }

    public static void findCombine(int n, int inputData[], int start, int end,
                                   int marksArr[], int index, int size, boolean change) {
        if (0 == n && change) {
            for (int i = 0; i <= index; ++i) {
                System.out.print(marksArr[i] + " ");
            }
            System.out.println();
        }

        // 防止0，不跳出
        if (start < end && index < size - 1) {
            if (n >= inputData[start]) {
                ++index;
                marksArr[index] = inputData[start];
                findCombine(n - inputData[start], inputData, start + 1, end, marksArr, index, size, true);
                --index;
            }
            findCombine(n, inputData, start + 1, end, marksArr, index, size, false);
        }
    }
}
